package com.enjoy.rec;

import org.junit.Test;

/**
 * 斐波那契数列又称黄金分割数列
 * 1,1,2,3,5,8,13,21,34
 * 这个数列从第3项开始，每一项都等于前两项之和
 */
public class Fibonacci {

    //普通递归
    public int fib(int n) {
        if (n < 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public int noRec(int n) {
        // 循环
        if (n < 2) {
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;

        for (int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }


    public int fib2(){

        return 0;
    }

    @Test
    public void test1() {
        for (int i = 0; i < 45; i++) {
            long start = System.currentTimeMillis();
            System.out.println("第" + i + "数:" + fib(i) + " 所花费的时间为 " + (System.currentTimeMillis() - start) + "ms");
        }
    }

    @Test
    public void test2() {
        for (int i = 0; i < 45; i++) {
            long start = System.currentTimeMillis();
            System.out.println("第" + i + "数:" + noRec(i) + " 所花费的时间为 " + (System.currentTimeMillis() - start) + "ms");
        }
    }
}
